//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 
//
// 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/ 
// Related Topics 递归 链表 👍 363 👎 0

package com.cute.leetcode.editor.cn;
public class FanZhuanLianBiaoLcof {
    public static void main(String[] args) {
        Solution solution = new FanZhuanLianBiaoLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 头插法，创建一个空的链表头，最终返回头节点的下一个节点
     */
    public ListNode reverseList1(ListNode head) {
        ListNode res = new ListNode(-1);
        ListNode temp = null;
        while (head != null){
            res.next = new ListNode(head.val);
            res.next.next = temp;
            temp = res.next;
            head = head.next;
        }
        return res.next;
    }

    /**
     * 剑指Offer中的题解，使用三个节点来存储当前节点，反转链表头，后续链表头三部分信息
     */
    public ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        ListNode curNode = head;
        ListNode nextNode;
        while (curNode != null){
            nextNode = curNode.next;// 保存后续链表信息
            curNode.next = preNode;// 修改当前节点为头部
            preNode = curNode;// 储存反转链表的头部
            curNode = nextNode;// 指向下一节点
        }
        return preNode;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}